#! usr/bin/env python
#-*- coding: UTF-8 -*-
import heapq
import math

def distancia_entre_puntos(x1,x2,y1,y2):
	return math.sqrt((x1-y1)**2+(x2-y2)**2)
	

def dijkstra(grafo, origen, destino=None, p=0):
	
    if origen == destino: return (0, [origen])
    distancias = {}  # diccionario con las distancias finales
    caminos = {}  # diccionario de caminos
    pesos = {}
    heap = [] # usa heapq con tuplas de (distancia,nodo) 
    heapq.heappush(heap,(0,origen, []))
    padre = origen
    while heap:
        (peso,vert,camino)=heapq.heappop(heap)
        if vert in pesos: continue # ya está listo
        pesos[vert] = peso
        caminos[vert] = camino
        distancias[vert] = distancia_entre_puntos(float(vert.datos[1]), float(vert.datos[2]),float(padre.datos[1]), float(padre.datos[2]))
        if vert == destino: break # Si ya llegue salgo
        for dest, datos in grafo.aristas(vert):
            v_peso = pesos[vert] + int(datos[p]) #p = posición del valor peso en datos
            camino = caminos[vert]+[dest]
            padre = vert
            heapq.heappush(heap,(v_peso, dest, camino))
    return (pesos, distancias,caminos)

